package com.uow.algdemo.algorithms;

import java.util.ArrayList;
import java.util.List;

/**
 * This class will receive data of the queens problem and solve the problem, then generate animation steps.
 */
public class Queen
{
    /**
     * This is the number of queens for this problem.
     */
	private int total;
    /**
     * This is status of algorithm already finished or not.
     */
	private boolean finished = false;
    /**
     * This array contains queens' position.
     */
    private int[] queens;
    /**
     * This array contains does a row exists queen.
     */
    private boolean[] rowExists;
    /**
     * This array contains does a row from left bottom to right top exists queen.
     */
    private boolean[] a;
    /**
     * This array contains does a row from left top to right bottom exists queen.
     */
    private boolean[] b;
    /**
     * This array contains steps of the queen problem solution animation.
     */
	private List<int[][]> steps = new ArrayList<int[][]>();
	
    /**
     * @param n Number of queens.
     */
	public Queen(int n)
	{
		total = n;
		rowExists = new boolean[total + 1];
		queens = new int[total + 1];
		a = new boolean[total * 2];
		b = new boolean[total * 2];
	}
	/**
	 * @return The steps of solution.
	 */
	public List<int[][]> getSteps()
	{
		return steps;
	}
    /**
     * This method records steps for place a queen on chess board.
     * @param x Coordinate of horizontal.
     * @param y Coordinate of vertical.
     */
	private void place(int x, int y)
	{
		if(!finished)
		{
			int[][] step = new int[2][2];
			step[0][0] = 0;
			step[1][0] = x-1;
			step[1][1] = y-1;
			
			steps.add(step);
		}
	}
    /**
     * This method records steps for delete a queen from chess board.
     * @param x Coordinate of horizontal.
     * @param y Coordinate of vertical.
     */
	private void delete(int x, int y)
	{
		if(!finished)
		{
			int[][] step = new int[2][2];
			step[0][0] = 1;
			step[1][0] = x-1;
			step[1][1] = y-1;
			
			steps.add(step);
		}
	}
    /**
     * This method check is position valid for placing a queen.
     * @param row Index of row.
     * @param col Index of column.
     */
    private boolean isExists(int row, int col)
    {
        return (rowExists[row] || a[row + col - 1] || b[total + col - row]);
    }

    /**
     * This method is main function for back tracking.
     * @param col Index of column start.
     */
    public void testing(int col)
    {
        for (int row = 1; row < total + 1; row++)
        {
            place(col,row);
            if (!isExists(row, col))
            {
                queens[col] = row;
                rowExists[row] = a[row + col - 1] = b[total + col - row] = true;
                
                if(col == total)
                {
                    finished = true;
                    return;
                }
                else
                {
                    testing(col + 1);
                }
                rowExists[row] = a[row + col - 1] = b[total + col - row] = false;
                delete(col,row);
            }
            else
            {
            	delete(col,row);
            }
        }
    }
	/**
     * This method solve the queens' back tracking problem and records all steps in list of steps.
     */
	public void backTracking()
	{
        for (int i = 0; i < total + 1; i++)
        {
            rowExists[i] = false;
        }
        
        for(int i = 0; i < total * 2; i++)
        {
            a[i] = b[i] = false;
        }
		testing(1);
	}
}
